Section: Research Program

Structure of random networks

This line of research aims at understanding the global structure of stochastic networks (connectivity, magnitude of distances, etc) via models of random graphs. It consists of two complementary foundational and applied aspects of connectivity.

Random graphs, statistical physics and combinatorial optimization. The connectivity of usual models for networks based on random graphs models (Erdős–Rényi and random geometric graphs) may be tuned by adjusting the average degree. There is a phase transition as the average degree approaches one, a giant connected component containing a positive proportion of the nodes suddenly appears. The phase of practical interest is the supercritical one, when there is at least a giant component, while the theoretical interest lies at the critical phase, the break-point just before it appears.

At the critical point there is not yet a macroscopic component and the network consists of a large number of connected component at the mesoscopic scale. From a theoretical point of view, this phase is most interesting since the structure of the clusters there is expected (heuristically) to be universal. Understanding this phase and its universality is a great challenge that would impact the knowledge of phase transitions in all high-dimensional models of statistical physics and combinatorial optimization.

Random geometric graphs and wireless networks. The level of connection of the network is of course crucial, but the scalability imposes that the underlying graph also be sparse: trade offs must be made, which required a fine evaluation of the costs/benefits. Various direct and indirect measures of connectivity are crucial to these choices: What is the size of the overwhelming connected component? When does complete connectivity occur? What is the order of magnitude of distances? Are paths to a target easy to find using only local information? Are there simple broadcasting algorithms? Can one put an end to viral infections? How much time for a random crawler to see most of the network?

Navigation and point location in random meshes. Other applications which are less directly related to networks include the design of improved navigation or point location algorithms in geometric meshes such as the Delaunay triangulation build from random point sets. There the graph model is essentially fixed, but the constraints it imposes raise a number of challenging problems. The aim is to prove performance guarantees for these algorithms which are used in most manipulations of the meshes.